class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if (stones.size() < 2) return stones[0];
        int sum = 0;
        for (auto x : stones) sum += x;
        int val = sum >> 1;
        vector<int> dp(1505);
        dp[0] = 0;
        for (int i = 0; i < stones.size(); i++) {
            for (int j = val; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[val] - dp[val];
    }
};
